home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / smaltalk / gnu_st.lha / gnu_st / smalltalk-1.1.1 / IdentityDictionary.st < prev    next >
Text File  |  1991-09-12  |  8KB  |  297 lines
  1. "======================================================================
  2. |
  3. |   IdentityDictionary Method Definitions
  4. |
  5.  ======================================================================"
  6.  
  7.  
  8. "======================================================================
  9. |
  10. | Copyright (C) 1990, 1991 Free Software Foundation, Inc.
  11. | Written by Steve Byrne.
  12. |
  13. | This file is part of GNU Smalltalk.
  14. |
  15. | GNU Smalltalk is free software; you can redistribute it and/or modify it
  16. | under the terms of the GNU General Public License as published by the Free
  17. | Software Foundation; either version 1, or (at your option) any later version.
  18. | 
  19. | GNU Smalltalk is distributed in the hope that it will be useful, but WITHOUT
  20. | ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  21. | FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
  22. | details.
  23. | 
  24. | You should have received a copy of the GNU General Public License along with
  25. | GNU Smalltalk; see the file COPYING.  If not, write to the Free Software
  26. | Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  
  27. |
  28.  ======================================================================"
  29.  
  30.  
  31. "
  32. |     Change Log
  33. | ============================================================================
  34. | Author       Date       Change 
  35. | sbyrne     25 Apr 89      created.
  36. |
  37. "
  38.  
  39. Dictionary variableSubclass: #IdentityDictionary
  40.        instanceVariableNames: 'values'
  41.        classVariableNames: ''
  42.        poolDictionaries: ''
  43.        category: nil.
  44.  
  45. IdentityDictionary comment:
  46. 'I am similar to dictionary, except that my representation is
  47. different, and I use the object identity comparision message == to
  48. determine equivalence of indices.' !
  49.  
  50. !IdentityDictionary class methodsFor: 'instance creation'!
  51.  
  52. new
  53.     ^self new: 4
  54. !
  55.  
  56. new: anInteger
  57.     ^(super new: anInteger) initValues
  58.  
  59. !!
  60.  
  61.  
  62.  
  63. !IdentityDictionary methodsFor: 'accessing'!
  64.  
  65. add: anAssociation
  66.     self at: anAssociation key put: anAssociation value.
  67.     ^anAssociation
  68. !
  69.  
  70. at: key put: value
  71.     | index |
  72.     index _ self findKeyIndex: key.
  73.     (self basicAt: index) isNil
  74.         ifTrue: [ tally _ tally + 1 ].
  75.     self basicAt: index put: key.
  76.     values basicAt: index put: value.
  77.     ^value
  78. !
  79.  
  80. at: key ifAbsent: aBlock
  81.     | index |
  82.     index _ self findKeyIndex: key.
  83.     (self basicAt: index) isNil
  84.         ifTrue: [ ^aBlock value ].
  85.     ^values basicAt: index
  86. !    
  87.     
  88. associationAt: key ifAbsent: aBlock
  89.     | index assoc|
  90.     ^Association key: key
  91.          value: (self at: key
  92.                       ifAbsent: [ ^aBlock value ])
  93. !
  94.  
  95. keyAtValue: value ifAbsent: exceptionBlock
  96.     self indicesDo:
  97.         [ :i | value = (values basicAt: i)
  98.                  ifTrue: [ ^self basicAt: i] ].
  99.     ^exceptionBlock value
  100. !!
  101.  
  102.  
  103.  
  104. !IdentityDictionary methodsFor: 'dictionary testing'!
  105. includesAssociation: anAssociation
  106.     | index |
  107.     index _ self findKeyIndex: anAssociation key.
  108.     ^(self basicAt: index) notNil
  109.         and: [ (values basicAt: index) = anAssociation value ]
  110. !
  111.  
  112. includesKey: key
  113.     ^(self basicAt: (self findKeyIndex: key)) notNil
  114. !!
  115.  
  116.  
  117.  
  118. !IdentityDictionary methodsFor: 'dictionary removing'!
  119. removeKey: key ifAbsent: aBlock
  120.     | index value|
  121.     index _ self findKeyIndexNoGrow: key ifAbsent: [ ^aBlock value ].
  122.     value _ values basicAt: index.
  123.     self basicAt: index put: nil.
  124.     values basicAt: index put: nil.
  125.     tally _ tally - 1.
  126.     self rehashObjectsAfter: index.
  127.     ^ value
  128. !!
  129.  
  130.  
  131.  
  132. !IdentityDictionary methodsFor: 'dictionary enumerating'!
  133. associationsDo: aBlock
  134.     self indicesDo:
  135.         [ :i | aBlock value: (Association key: (self basicAt: i)
  136.                                       value: (values basicAt: i)) ]
  137. !
  138.  
  139. "These could be implemented more efficiently by 
  140.  doing the explicit scanning of the dictionary by hand"
  141. keysDo: aBlock
  142.     self indicesDo: [ :i | aBlock value: (self basicAt: i) ]
  143. !
  144.  
  145. do: aBlock
  146.     self indicesDo: [ :i | aBlock value: (values basicAt: i) ]
  147. !
  148.  
  149. select: aBlock
  150.     | newDict |
  151.     newDict _ self species new.
  152.     self indicesDo:
  153.         [ :i | (aBlock value: (values basicAt: i))
  154.                  ifTrue: [ newDict add: (Association key: (self basicAt: i)
  155.                                             value: (values basicAt: i))] ].
  156.     ^newDict
  157. !!
  158.  
  159.  
  160.  
  161. !IdentityDictionary methodsFor: 'misc math methods'!
  162.  
  163. = aDictionary
  164.     tally ~= aDictionary size ifTrue: [ ^false ].
  165.     self indicesDo:
  166.         [ :i | (values basicAt: i) = (aDictionary at: (self basicAt: i)
  167.                                               ifAbsent: [ ^false ])
  168.                  ifFalse: [ ^false ] ].
  169.     ^true
  170. !
  171.  
  172. hash
  173.     | hashValue |
  174.     hashValue _ tally.
  175.     self indicesDo:
  176.         [ :i | hashValue _ hashValue + (self basicAt: i) hash.
  177.            hashValue _ hashValue + (values basicAt: i) hash ].
  178.     ^hashValue
  179. !!
  180.  
  181.  
  182.  
  183. !IdentityDictionary methodsFor: 'printing'!
  184.  
  185. printOn: aStream
  186.     aStream nextPutAll: self class name , ' (' .
  187.     aStream nl.
  188.     self indicesDo:
  189.         [ :i | aStream tab.
  190.            (self basicAt: i) storeOn: aStream.
  191.            aStream nextPut: $,.
  192.            (values basicAt: i) storeOn: aStream.
  193.            aStream nl ].
  194.     aStream nextPut: $)
  195. !!
  196.  
  197.  
  198.  
  199. !IdentityDictionary methodsFor: 'storing'!
  200.  
  201. storeOn: aStream
  202.     | hasElements |
  203.     aStream nextPutAll: '(', self class name , ' new'.
  204.     hasElements _ false.
  205.     self indicesDo:
  206.         [ :i | aStream nextPutAll: ' at: '.
  207.                (self basicAt: i) storeOn: aStream.
  208.            aStream nextPutAll: ' put: '.
  209.                (values basicAt: i) storeOn: aStream.
  210.            aStream nextPut: $;.
  211.            hasElements _ true ].
  212.     hasElements ifTrue: [ aStream nextPutAll: ' yourself' ].
  213.     aStream nextPut: $)
  214. !!
  215.  
  216.  
  217.  
  218. !IdentityDictionary methodsFor: 'private methods'!
  219.  
  220. initValues
  221.     values _ Array new: self basicSize
  222. !
  223.  
  224. indicesDo: aBlock
  225.     "Invokes aBlock with all the indices of the set that have valid keys"
  226.     1 to: self basicSize do:
  227.         [ :i | (self basicAt: i) notNil
  228.               ifTrue: [ aBlock value: i ] ]
  229. !    
  230.  
  231. rehashObjectsAfter: index
  232.     "### rehash bug needs to be fixed!!!!"
  233.     "Rehashes all the objects in the collection after index to see if any of
  234.     them hash to index.  If so, that object is copied to index, and the
  235.     process repeats with that object's index, until a nil is encountered."
  236.     | i size count key |
  237.     i _ index.
  238.     size _ self basicSize.
  239.     count _ size.
  240.     [ count > 0 ]
  241.         whileTrue:
  242.         [ i _ i \\ size + 1.
  243.               key _ self basicAt: i.
  244.           key isNil ifTrue: [ ^self ].
  245.               ((key hash \\ size) + 1) = index
  246.               ifTrue: [ self basicAt: index put: key.
  247.                   values basicAt: index put: (values basicAt: i).
  248.                   self basicAt: i put: nil.  "Be tidy"
  249.               values basicAt: i put: nil."Be tidy"
  250.               index _ i ].
  251.               count _ count - 1 ]
  252. !
  253.  
  254. findKeyIndex: aKey ifFull: aBlock
  255.     "Tries to see if aKey exists as the key of an indexed variable (which is an
  256.     association).  If it's searched the entire dictionary and the key is 
  257.     not to be found, aBlock is evaluated and it's value is returned."
  258.     | index count size key |
  259.     size _ self basicSize.
  260.     index _ aKey hash \\ size + 1.
  261.     count _ size.
  262.     [ count > 0 ]
  263.         whileTrue:
  264.         [ key _ self basicAt: index.
  265.               (key isNil or: [ key == aKey ])
  266.             ifTrue: [ ^index ].
  267.           index _ index \\ size + 1.
  268.           count _ count - 1. ].
  269.     ^aBlock value
  270. !
  271.         
  272. findKeyIndex: aKey
  273.     "Finds an association with the given key in the dictionary and returns its
  274.     index.  If the dictionary doesn't contain the object and there is no nil
  275.     element, the dictionary is grown and then the index of where the object
  276.     would go is returned."
  277.     ^self findKeyIndex: aKey
  278.            ifFull: [ self grow.
  279.                 self findKeyIndexNoGrow: aKey
  280.                   ifAbsent: [ ^self error: 'failed to grow a new empty element!!!' ] ]
  281. !
  282.  
  283. grow
  284.     | newDict |
  285.     newDict _ self species new: self basicSize + self growSize.
  286.     self indicesDo: [ :i | newDict at: (self basicAt: i)
  287.                    put: (values basicAt: i) ].
  288.     ^self become: newDict
  289. !
  290.  
  291. growSize
  292.     ^32
  293.  
  294. !!
  295.  
  296.  
  297.